// @before-stub-for-debug-begin
#include <string>
#include <vector>

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=763 lang=cpp
 *
 * [763] 划分字母区间
 *
 * https://leetcode-cn.com/problems/partition-labels/description/
 *
 * algorithms
 * Medium (76.43%)
 * Likes:    701
 * Dislikes: 0
 * Total Accepted:    107.2K
 * Total Submissions: 140.2K
 * Testcase Example:  '"ababcbacadefegdehijhklij"'
 *
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
 *
 *
 *
 * 示例：
 *
 *
 * 输入：S = "ababcbacadefegdehijhklij"
 * 输出：[9,7,8]
 * 解释：
 * 划分结果为 "ababcbaca", "defegde", "hijhklij"。
 * 每个字母最多出现在一个片段中。
 * 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 *
 *
 *
 *
 * 提示：
 *
 *
 * S的长度在[1, 500]之间。
 * S只包含小写字母 'a' 到 'z' 。
 *
 *
 */

// @lc code=start
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.length();
        vector<int> singleChara{-1, -1};
        vector<vector<int>> Chara(26, singleChara);
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int index = s[i] - 'a';
            // 第一次出现
            if (Chara[index][0] == -1) {
                Chara[index][0] = i;
                Chara[index][1] = i;
            }
            // 后面出现
            else {
                Chara[index][1] = i;
            }
        }
        sort(Chara.begin(), Chara.end(), [](vector<int> &a, vector<int> &b) { return a[0] < b[0]; });
        int flag = 0;
        int left = -1, right = -1;
        for (int i = 0; i < 26; ++i) {
            if (Chara[i][0] != -1) {
                if (Chara[i][0] < right) {
                    right = max(Chara[i][1], right);
                }
                else {
                    if (flag == 1) {
                        ans.push_back(right - left + 1);
                    }
                    left = Chara[i][0];
                    right = Chara[i][1];
                    flag = 1;
                }
            }
        }
        ans.push_back(right - left + 1);
        return ans;
    }
};
// @lc code=end
